package Algorithms.DynamicPrograming_03;

/*
 * @Author 罗
 * @date 2020/3/29 - 2:49 下午
 *
 */

/**
 * 动态规划算法 （背包问题）
 */
public class DynamicPrograming {

    public static int[][] dynamicPrograming(Item[] items, int maxCapacity) {

        int combineItemsValue;
        /*
         * 用于记录本行本列对应的上一行的总价格
         * */
        int lastRowValue;
        /*
         *
         * 新建一个动态规划表
         *
         * 二维数组的下标是商品数组items[]中的商品
         *      items.length不用+1是因为，传进来的items[]已经+1过了
         * 一维数组的下标是商品的重量
         *      行和列都+1，为了让第一行和第一列的值都为0，方便公式的套用
         *
         * 数组对应的value为，当背包容量是capacity时，前item个物品所能形成的最大价值
         * */
        int[][] presentValue = new int[items.length][maxCapacity + 1];
        /*
         * 要的结果不仅是总价格，而且还要背包的每一个单元格放了些什么
         * */
        int[][] recordItems = new int[presentValue.length][presentValue[0].length];
        /*
         * 遍历物品
         * */
        for (int item = 1; item < presentValue.length; item++) {
            /*
             * 遍历每个物品对应的重量
             * 第一行及第一列默认就是0，所以不用特意初始化
             * item = 1 跳过第一行的初始化
             * capacity = 1 跳过第一列的初始化
             * */
            for (int capacity = 1; capacity < presentValue[item].length; capacity++) {
                /*
                 * 把新物品添加进去之后依然有剩余空间（重量），可以用来摆放其他物品
                 * */
                if (capacity >= items[item].getWeight()) {
                    /*
                     * 新商品加进来之后
                     * 比较本列与本行交点，的上一行的value
                     * */
                    /*presentValue[item][capacity] = Math.max(presentValue[item - 1][capacity],
                            items[item].getValue() + presentValue[item - 1][capacity - items[item].getWeight()]);*/
                    /*
                     * 要具体知道究竟是那一个的总价值高，就不能用Math.max()了，需要使用if else
                     * */
                    lastRowValue = presentValue[item - 1][capacity];
                    /*
                     * 组合物品的总价值 = 新添加物品的价格 + 对应上一行，对应的剩余容量下标(剩余容量 = 本行列总容量 - 新添加物品的容量)的物品价格
                     * 剩余容量 = capacity - items[item].getWeight()
                     * 放入新添加物品之后，还能继续放入的物品价值 = presentValue[上一行][剩余容量]
                     * */
                    combineItemsValue = items[item].getValue() + presentValue[item - 1][capacity - items[item].getWeight()];
                    if (lastRowValue > combineItemsValue) {
                        presentValue[item][capacity] = lastRowValue;

                    } else {
                        presentValue[item][capacity] = combineItemsValue;
                        /*
                         * 把当前的情况记录到数组
                         * */
                        recordItems[item][capacity] = 1;
                    }
                } else if (capacity < items[item].getWeight()) {
                    // 准备加入的新增物品容量<=当前背包的容量
                    // 就使用上一行的最优解作为这一行的最优解
                    presentValue[item][capacity] = presentValue[item - 1][capacity];
                }

            }
        }
        /*
        遍历recordItems，这样会把所有的放入情况都得到，其实我们只需要最后的放入结果
        for (int i = 0; i < recordItems.length; i++) {
            for (int j = 0; j < recordItems[i].length; j++) {

                if(recordItems[i][j]==1){
                    System.out.println("第"+i + "个物品放入背包");
                }
            }
        }*/
        /*
         * 查看价值最高的放法中，背包中放入了些什么
         *   从最后开始遍历
         * */
        int item = presentValue.length - 1;
        int capacity = presentValue[0].length - 1;
        while (item > 0 && capacity > 0) {
            if (recordItems[item][capacity] == 1) {
                System.out.println("第" + item + "个物品放入背包");
                /*
                 * 放入背包之后，容量 = 原容量 - 放入背包物品的容量
                 * */
                capacity = capacity - items[item].getWeight();
            }
            /*
             * 不管该商品是否能放入背包，都要切换到下一个商品，以检测能否放入
             * */
            item--;
        }
        return presentValue;
    }
}
